package leetcode.other.sort;

import java.util.Arrays;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/9/11 15:09
 */
public class _面试题_17_08_马戏团人塔 {

    public static void main(String[] args) {
        new _面试题_17_08_马戏团人塔().bestSeqAtIndex(new int[]{
                65,65,56,75,60,68
        }, new int[] {
                100,150,90,190,95,110
        });
    }

    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len = height.length;
        int[][] persons = new int[len][2];
        for (int i = 0; i < len; i++) {
            persons[i] = new int[]{height[i], weight[i]};
        }

        Arrays.sort(persons, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(b[0], a[0]);
        });
        System.out.println(Arrays.deepToString(persons));
        int[][] dp = new int[len + 1][2];
        int index = 1;
        dp[index] = persons[0];
        for (int i = 1; i < len; i++) {
            if (persons[i][1] < dp[index][1]) {
                dp[++index] = persons[i];
            } else {
                int pos = find(dp, persons[i], index);
                dp[pos] = persons[i];
            }
        }
        return index;
    }

    public int find(int[][] dp, int[] person, int index) {
        int left = 1;
        int right = index; // 顶
        while (left < right) {
            int mid = (left + right) >> 1;
            if (dp[mid][1] <= person[1]) { // person[1] 当前的人的体重
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return right;
    }
}
